package com.practice.niuke.new_direct_basics.class09;

import java.util.HashMap;

/**
 * 设计RandomPool结构
 * 【题目】
 * 设计一种结构， 在该结构中有如下三个功能:
 * insert(key):将某个key加入到该结构， 做到不重复加入
 * delete(key):将原本在结构中的某个key移除
 * getRandom(): 等概率随机返回结构中的任何一个key。
 * 【要求】
 * Insert、 delete和getRandom方法的时间复杂度都是O(1)
 */
public class Code02_RandomPool {

    /**
     * 使用两个HashMap来设计这个结构，HashMap<K, Integer>和HashMap<Integer, K>，
     *
     * 删除数据时要用最后一个key去填充被删掉的那个key
     *
     * @param <K>
     */
    public static class Pool<K> {
        private HashMap<K, Integer> keyIndexMap;
        private HashMap<Integer, K> indexKeyMap;
        private int size;

        /**
         * 初始化这个结构，此时size=0
         */
        public Pool() {
            this.keyIndexMap = new HashMap<K, Integer>();
            this.indexKeyMap = new HashMap<Integer, K>();
            this.size = 0;
        }

        /**
         * 往这个结构中插入一条记录
         *
         * @param key
         */
        public void insert(K key) {
            if (!this.keyIndexMap.containsKey(key)) {
                // 在keyIndexMap中，以插入的这个K类型的量为key，以目前的size为value
                this.keyIndexMap.put(key, this.size);
                // 在indexKeyMap中，以目前的size为key，以插入的这个K类型的量为value，之后size+1
                this.indexKeyMap.put(this.size++, key);
            }
        }

        /**
         * 从这个结构中删除一条记录
         *
         * @param key
         */
        public void delete(K key) {
            if (this.keyIndexMap.containsKey(key)) {
                // 在keyIndexMap中获得要删除的这条记录的value值
                int deleteIndex = this.keyIndexMap.get(key);
                // 在keyIndexMap中最后一条记录的value一定为size-1
                int lastIndex = --this.size;
                // indexKeyMap中，根据上一步得到的在keyIndexMap中最后一条记录的value，
                // 获得其keyIndexMap中的key值
                K lastKey = this.indexKeyMap.get(lastIndex);
                
                // 将keyIndexMap中，最后一条记录的value，设置为要删除的这条记录的value值
                this.keyIndexMap.put(lastKey, deleteIndex);
                // 将indexKeyMap中，与keyIndexMap中要删除的这条记录的value值相同的key的value值，
                // 设置为在keyIndexMap中最后一条记录key
                this.indexKeyMap.put(deleteIndex, lastKey);
                // 在keyIndexMap删除要删除的这条记录
                this.keyIndexMap.remove(key);
                // 在indexKeyMap中删除，在keyIndexMap中最后一条记录的value为key 的 记录
                this.indexKeyMap.remove(lastIndex);
            }
        }

        /**
         * 等概率随机返回结构中的任何一个key
         *
         * @return
         */
        public K getRandom() {
            if (this.size == 0) {
                return null;
            }
            // 随机等概率的得到一个0 ~ size -1上的数
            int randomIndex = (int) (Math.random() * this.size); // 0 ~ size -1
            // 获取记录
            return this.indexKeyMap.get(randomIndex);
        }

    }

    public static void main(String[] args) {
        Pool<String> pool = new Pool<String>();
        pool.insert("zuo");
        pool.insert("cheng");
        pool.insert("yun");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());

    }

}
